'''
Created on Feb 5, 2011

@author: Andresin
'''

class SudokuCell :
    def __init__( self, row, col, initValue = None ) : # holy cow! I can edit online!
        """Initializes a new sudoku cell, all posibilities are there
           The possible values are actually kept as a set of values from [1..9] """
        self.__initValue = initValue
        self.__row = row
        self.__col = col
        if self.__initValue != None :
            self._pos = set( [ int( self.__initValue ) ] )
        else :
            self._pos = set( range( 1, 10 ) )
        
    def isSolved( self ) :
        return len( self._pos ) == 1    
    
    def solve( self, value ) :
        self._pos = set( [ value ] )    
    
    def reducePos( self, value ) :
        self._pos = self._pos.difference( set( [ value ] ) )
        
    def getPosition( self ) :
        return ( self.__row, self.__col )
    
    def getCell( self ) :
        return ( self.__row / 3, self.__col / 3 )
    
    def getNeighborsPositions( self ) :
        np = [ ]
        
        # get neigbohrs in the same row
        for c in range( 0, 9 ) :
            if c == self.__col : continue
            np.append( ( self.__row, c ) )
        
        # get neighbors in the same column
        for r in range( 0, 9 ) :
            if r == self.__row : continue
            np.append( ( r, self.__col ) )
        
        # get neibohrs in the same cell
        cell = self.getCell( )
        for r in range( 3 * cell[ 0 ], 3 * cell[ 0 ] + 3 ) :
            for c in range( 3 * cell[ 1 ], 3 * cell[ 1 ] + 3 ) :
                if ( r, c ) != self.getPosition( ) and np.count( ( r, c ) ) == 0 :
                    np.append( ( r, c ) )
                        
        return np
            
    def getValue( self ) :
        if self.isSolved( ) :
            return int( self.__str__( ) )
        else :
            return None
        
    def getPosString( self ) :
        ps = ""
        for i in range( 1, 10 ) :
            if i in self._pos :
                ps += str( i )
            else :
                ps += "x"
        return ps
            
        
    def __str__( self ) :
        if self.isSolved( ) :
            sol = self._pos.pop( )
            self._pos.add( sol )
            return str( sol )
        else :
            return '?'
    
class SudokuBoard :

    SIZE = 9
    
    def __init__( self, initString = None ):
        """Initializes a new sudoku board with 9x9 array of new cells"""
        self.__solvedCells = [ ]
        self.__table = [ ]

        if len( initString ) != SudokuBoard.SIZE * SudokuBoard.SIZE :
            initString = None
        
        for r in range( 0, 9 ) :
            row = [ ]
            for c in range( 0, 9 ) :
                if initString != None and initString[ r * SudokuBoard.SIZE + c ] != '?' :
                    cell = SudokuCell( r, c, initString[ r * SudokuBoard.SIZE + c ] )
                    row.append( cell )
                    self.__solvedCells.append( cell )
                else :
                    row.append( SudokuCell( r, c ) )
            self.__table.append( row )
            
    def isSolved( self ) :
        return len( self.__solvedCells ) == SudokuBoard.SIZE * SudokuBoard.SIZE 
    
    def solve( self ) :
        workingSet = list( self.__solvedCells )

        self.printPosibilities( )
        
        while len( workingSet ) > 0 :
            cell = workingSet.pop( 0 )
            for ( neighborR, neighborC ) in cell.getNeighborsPositions( ) :
                neighbor = self.__table[ neighborR ][ neighborC ]
                neighborChanged = neighbor.reducePos( cell.getValue( ) )
                
                if neighbor.isSolved( ) and self.__solvedCells.count( neighbor ) == 0 :
                    workingSet.append( neighbor )
                    self.__solvedCells.append( neighbor )
                    
                # If there was a change, also check in the neighbor's neighbors
                # if something has opened up
                if neighborChanged :
                    for newS in self.scourForSolved( neighbor ) :
                        if( self.__solvedCells.count( newS ) == 0 ) :
                            self.__solvedCells.append( newS )
                    
            self.printPosibilities( )
        
    def scourForSolved( self, sudokuCell ) :
        answer = [ ]
        
        # go through the row and if there are values that are only possible
        # in a column, those are solved
        
        iniD = dict( [ ( i, 0 ) for i in range( 1, 10 ) ] )
        for c in range( 0, 9 ) :
            for p in self.__table[ sudokuCell.getPosition( )[ 0 ], c ]._pos :
                iniD[ p ] += 1;
        for ( k, v ) in iniD :
            if v == 1 :
                self.__table[ sudokuCell.getPosition( )[ 0 ], c ].solve( k )
                answer.append( self.__table[ sudokuCell.getPosition( )[ 0 ], c ] )
                
        iniD = dict( [ ( i, 0 ) for i in range( 1, 10 ) ] )
        for r in range( 0, 9 ) :
            for p in self.__table[ r, sudokuCell.getPosition( )[ 1 ] ]._pos :
                iniD[ p ] += 1;
        for ( k, v ) in iniD :
            if v == 1 :
                self.__table[ r, sudokuCell.getPosition( )[ 1 ] ].solve( k )
                answer.append( self.__table[ r, sudokuCell.getPosition( )[ 1 ] ] )
                
        iniD = dict( [ ( i, 0 ) for i in range( 1, 10 ) ] )
        for r in range( 3 * sudokuCell.getPosition( )[ 0 ], 3 * sudokuCell.getPosition( )[ 0 ] + 3 ) :
            for c in range( 3 * sudokuCell.getPosition( )[ 1 ], 3 * sudokuCell.getPosition( )[ 1 ] + 3 ) :
                if ( r, c ) != sudokuCell.getPosition( ) :
                    for p in self.__table[ r, c ]._pos :
                        iniD[ p ] += 1
        for ( k, v ) in iniD :
            if v == 1 :
                self.__table[ sudokuCell.getPosition( )[ 0 ], c ].solve( k )
                answer.append( self.__table[ sudokuCell.getPosition( )[ 0 ], c ] )
                    
        return answer
        
    def printNice(self ) :
        print "+---"*9 + "+"
        for i in range( 0, 9 ) :
            print "|", " | ".join( [ str( c ) for c in self.__table[i] ] ), "|"
            print "+---"*9 + "+"
            
    def printPosibilities( self ) :
        sep = ( "|" + "-" * 9 ) * 9 + "|"
        print sep
        for i in range( 0, 9 ) :
            print "|" + "|".join( [  c.getPosString( ) for c in self.__table[ i ] ] ) + "|"
            print sep
    
if __name__ == "__main__":
    s = SudokuBoard( "?9??1?3?26?1???????2?8???91238?????74????8??3????3185?9????2?3???2??5?493?549??2?" )
    s.printNice( )

    s.printPosibilities( )

    s.solve( )
    
    s.printNice( )